/*
 * 6.3
 * You have a five quart jug and a three quart jug, and an unlimited supply of water
 * (but no measuring cups). How would you come up with exactly four quarts of water?
 * NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would
 * be impossible.
 */
#include <stdio.h>
#include <string.h>

const int asize = 3, bsize = 5, rsize = 4;
const int maxsize = 100;
int curr_status[maxsize][2];
int curr = 0;
int best_status[maxsize][2];
int best = -1;

/* first solution, find the first, but not the best solution. */
bool dfs()
{
    if (curr_status[curr][0] == rsize || curr_status[curr][1] == rsize) {
        return true;
    }
    int a = curr_status[curr][0], b = curr_status[curr][1];
    /* loop? */
    bool find = false;
    for (int i = 0; i < curr; i++) {
        if (curr_status[i][0] == a && curr_status[i][1] == b) {
            find = true;
        }
    }
    if (find) {
        return false;
    }
    /* cases */
    bool ret = false;
    curr++;
    if (a > 0) {
        curr_status[curr][0] = 0;
        curr_status[curr][1] = b;
        ret = dfs();
    }
    if (!ret && a < asize) {
        curr_status[curr][0] = asize;
        curr_status[curr][1] = b;
        ret = dfs();
    }
    if (!ret && b > 0) {
        curr_status[curr][1] = 0;
        curr_status[curr][0] = a;
        ret = dfs();
    }
    if (!ret && b < bsize) {
        curr_status[curr][1] = bsize;
        curr_status[curr][0] = a;
        ret = dfs();
    }
    if (!ret && a > 0 && b < bsize) {
        if (a + b <= bsize) {
            curr_status[curr][1] = b + a;
            curr_status[curr][0] = 0;
        } else {
            curr_status[curr][1] = bsize;
            curr_status[curr][0] = b + a - bsize;
        }
        ret = dfs();
    }
    if (!ret && a < asize && b > 0) {
        if (a + b <= asize) {
            curr_status[curr][0] = a + b;
            curr_status[curr][1] = 0;
        } else {
            curr_status[curr][0] = asize;
            curr_status[curr][1] = a + b - asize;
        }
        ret = dfs();
    }
    if (!ret) {
        curr--; /* backtracking */
    }
    return ret;
}

/*
 * second solution, find the best solution.
 * XXX: took too long time to finish...
 */
void dfs2()
{
    if (curr_status[curr][0] == rsize || curr_status[curr][1] == rsize) {
        if (best < 0 || curr < best) {
            best = curr;
            memcpy(best_status, curr_status, sizeof(int)*2*(curr+1));
        }
        return;
    }
    int a = curr_status[curr][0], b = curr_status[curr][1];
    /* loop? */
    bool find = false;
    for (int i = 0; i < curr; i++) {
        if (curr_status[i][0] == a && curr_status[i][1] == b) {
            return;
        }
    }
    /* cases */
    if (a > 0) {
        curr++;
        curr_status[curr][0] = 0;
        curr_status[curr][1] = b;
        dfs2();
        curr--; /* backtracking */
    }
    if (a < asize) {
        curr++;
        curr_status[curr][0] = asize;
        curr_status[curr][1] = b;
        dfs2();
        curr--; /* backtracking */
    }
    if (b > 0) {
        curr++;
        curr_status[curr][1] = 0;
        curr_status[curr][0] = a;
        dfs2();
        curr--;
    }
    if (b < bsize) {
        curr++;
        curr_status[curr][1] = bsize;
        curr_status[curr][0] = a;
        dfs2();
        curr--; /* backtracking */
    }
    if (a > 0 && b < bsize) {
        curr++;
        if (a + b <= bsize) {
            curr_status[curr][1] = b + a;
            curr_status[curr][0] = 0;
        } else {
            curr_status[curr][1] = bsize;
            curr_status[curr][0] = b + a - bsize;
        }
        dfs2();
        curr--; /* backtracking */
    }
    if (a < asize && b > 0) {
        curr++;
        if (a + b <= asize) {
            curr_status[curr][0] = a + b;
            curr_status[curr][1] = 0;
        } else {
            curr_status[curr][0] = asize;
            curr_status[curr][1] = a + b - asize;
        }
        dfs2();
        curr--; /* backtracking */
    }
}

int main()
{
#if 0
    dfs();
    if (curr > 0) {
        printf("(%d,%d)", curr_status[0][0], curr_status[0][1]);
        for (int i = 1; i <= curr; i++) {
            printf(" -> (%d,%d)", curr_status[i][0], curr_status[i][1]);
        }
        printf("\n");
    } else {
        printf("NOT FOUND\n");
    }
#else
    dfs2();
    if (best != -1) {
        printf("(%d,%d)", best_status[0][0], best_status[0][1]);
        for (int i = 1; i <= best; i++) {
            printf(" -> (%d,%d)", best_status[i][0], best_status[i][1]);
        }
        printf("\n");
    } else {
        printf("NOT FOUND\n");
    }
#endif
    return 0;
}
